Consider a three-dimensional scene consisting of a number of objects in some localized region with a background consisting of features distant from the objects in question. Software that models the objects from a set of calibrated photographs of the scene are known to the art. The models are typically used to generate a view of the scene as the scene would appear to a camera placed at a new location.
A typical prior art system is taught in W. B. Culbertson, T. Malzbender, and G. Slabaugh, “Generalized Voxel Coloring,” Vision Algorithms Theory and Practice (ICCV 1999 Workshop), Springer-Verlag Lecture Notes in Computer Science Vol. 1883, pp. 100-115, which is hereby incorporated by reference. These systems typically reconstruct a scene by defining a “reconstruction volume” containing the objects. This volume is then divided into volume elements referred to as “voxels”, which are the three-dimensional analog of pixels in two-dimensional image processing. If a voxel can be seen in a number of photographs, it is tested to determine if the voxel has the same color in each of the photographs in question. If the voxel has a consistent color, it is assigned that color. If the voxel is inconsistent, the voxel is assumed to be clear, i.e., the voxel is not part of any of the objects.
The algorithms are poorly suited to reconstructing large-scale scenes because the size of the reconstruction volume becomes unmanageable. A large scene requires a large reconstruction volume. The number of voxels that must be tested determines the computational workload. Hence, doubling the linear dimensions of the reconstruction volume increases the computational workload by a factor of 8. In addition, many scenes are effectively infinite. Consider an outdoor scene having a number of objects in the foreground and a distant background that includes a cloudy sky.
Systems that attempt to render infinite scenes are known to the art. These systems utilize environment maps that model the foreground and background separately. Environment maps have several drawbacks. First, the foreground and background are modeled differently and separate mechanisms must be provided to create and render each. Second, these algorithms do not provide any mechanism for dealing with a model object that exists in the foreground but also extends to the background (e.g. the ground or surface of the ocean). Such an object will appear to have a gap or discontinuity if modeled both as a foreground object and as part of the environment map. Objects at medium distances are also awkward to handle with environment maps. Either the size of the reconstruction volume must be increased to include them or they must be treated as though they are at infinity.
Broadly, it is the object of the present invention to provide an improved method for reconstructing three-dimensional scenes from a plurality of calibrated views of those scenes.
These and other objects of the present invention will become apparent to those skilled in the art from the following detailed description of the invention and the accompanying drawings.